package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.alibaba.fastjson.TypeReference;
import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;
import java.util.ArrayList;
import java.util.List;

public class NQueens {

    /**
     * 回溯
     * 每行依次遍历列，判断皇后是否在有效位置
     * 优化方案：使用chars来存储皇后的位置
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] chars = new char[n][n];
        solveNQueens(0, n, chars, res);
        return res;
    }

    public void solveNQueens(int index, int size, char[][] chars, List<List<String>> res) {
        if (index >= size) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < size; ++i){
                list.add(new String(chars[i]));
            }
            res.add(list);
            return;
        }
        for (int i = 0; i < size; ++i) {
            chars[index][i] = '.';
        }
        for (int i = 0; i < size; ++i) {
            if (isValid(chars, index, i)) {
                chars[index][i] = 'Q';
                solveNQueens(index + 1, size, chars, res);
                chars[index][i] = '.';
            }
        }
    }

    public boolean isValid(char[][] chars, int i, int j) {
        int size = chars.length;
        for (int x = 0; x < size; ++x) {
            if (chars[x][j] == 'Q') {
                return false;
            }
        }
        for (int y = 0; y < size; ++y) {
            if (chars[i][y] == 'Q') {
                return false;
            }
        }
        int x = i;
        int y = j;
        while (x >= 0 && y >= 0) {
            if (chars[x--][y--] == 'Q') {
                return false;
            }
        }
        x = i;
        y = j;
        while (x >= 0 && y < size) {
            if (chars[x--][y++] == 'Q') {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 4;
        List<List<String>> lists = new NQueens().solveNQueens(n);
        PrintUtils.println(lists);
        List<List<String>> lists2 = ArrayUtils.parse("[[\".Q..\",\"...Q\",\"Q...\",\"..Q.\"],[\"..Q.\",\"Q...\",\"...Q\",\".Q..\"]]");
        Assert.isTrue(ArrayUtils.allMatch(lists, lists2));
    }

}
